package com.tgy.programmer_code_interview_guide._02_linkedList;

/**
 * @Author: tgy
 * @Date: 1/22/21 10:54 AM
 */
public class _02_删除单链表和双链表的倒数第K个节点 {


    public static Node removeK(Node node, int k) {


        if (node == null || k <= 0) {

            return node;
        }

        Node front = node;

        // k - n
        while (front != null) {

            front = front.next;
            k--;
        }

        if (k > 0) {

            return node;
        }

        if (k == 0) {

            return node.next;
        }

        // -1 - (k - n)
        Node preNode = node;
        while (k < -1) {

            preNode = preNode.next;
            k++;
        }

        preNode.next = preNode.next.next;
        return node;
    }

    public static Node removeK01(Node node, int k) {

        if (node == null) {

            return node;
        }

        Node dummyNode = new Node();
        dummyNode.next = node;

        Node fastNode = dummyNode.next;

        while (k > 0 && fastNode != null) {

            fastNode = fastNode.next;
            k--;
        }

        // k 大于0则说明没有对应的倒数第k个节点
        if (k > 0) {

            return node;
        }

        // N - K
        Node preNode = dummyNode,curNode = dummyNode.next;

        while (fastNode != null) {

            preNode = curNode;
            curNode = curNode.next;
            fastNode = fastNode.next;
        }

        preNode.next = preNode.next.next;

        return dummyNode.next;
    }

    private static void printNode(Node node) {

        StringBuilder sb = new StringBuilder();
        while (node != null) {

            sb.append(node.val);
            sb.append(',');
            node = node.next;
        }

        System.out.println(sb.toString());
    }

    public static void main(String[] args) {

        Node root = new Node(1);
        root.next = new Node(2);
        root.next.next = new Node(3);
        root.next.next.next = new Node(4);

        root = removeK(root,5);
        printNode(root);
    }
}
